#include <bits/stdc++.h>
using namespace std;
// int n;
// int main()
// {
//     cin>>n;
//     vector<int> ret(n);
//     for(int i=0;i<n;i++)cin>>ret[i];
//     int count=0,i=0;
//     while(i<n)
//     {
//         if(i==n-1)
//         {
//             count++;
//             break;
//         }
//         if(ret[i+1]>ret[i])
//         {
//             while(i+1<n&&ret[i+1]>=ret[i])i++;
//             count++;
//         }
//         else if(ret[i+1]<ret[i])
//         {
//             while(i+1<n&&ret[i+1]<=ret[i])i++;
//             count++;
//         }
//         else while(i+1<n&&ret[i+1]==ret[i])i++;
//         i++;
//     }
//     cout<<count<<endl;
//     return 0;
// }
// int main()
// {
//     int x=1;
//     int T;cin>>T;
//     while(T--)
//     {
//         int H,count=0;cin>>H;
//         while(H)
//         {
//             H-=x;
//             count++;
//             if(H%(2*x)==0)x*=2;
//         }
//         cout<<count<<endl;
//     }
//     return 0;
// }
#include <queue>
class Solution {
public:
    int dp[100010]={0};
    int pos=0;
    int LIS(vector<int>& a) {
        for(auto x: a)
        {
            if(pos==0||x>dp[pos])
            {
                dp[++pos]=x;
            }
            else
            {
                int l=1,r=pos;
                while(l<r)
                {
                    int mid=l+(r-l)/2;
                    if(a[mid]>=x)r=mid;
                    else l=mid+1;
                }
                dp[l]=x;
            }
        }
        return pos;
    }
};
int main()
{
    vector<int> ret={2,2,2,2,49,90,1,56,3,4,5,0,456,267,0,90};
    cout<<Solution().LIS(ret)<<endl;
    return 0;
}